//package com.waitingresult.dfs;
//
//import java.util.Scanner;
//
///**
// * @Author: WangShuai
// * @CreateTime: 2023-03-19  19:36
// * @Description:
// * @Version: 1.0
// */
//public class DfsForCDemo2 {
//
//
//    //N为根据题目给出的最大数据范围 n表示总共有几个位置
//    public static int N = 20, n;
//    //g数组记录n*n棋盘
//    public static char[] g = new int[N][N];
//    //用col数组记录该列是否放置过皇后
//    public static boolean[] col = new boolean[N];
//    //用dg数组记录该正对角线是否放置过皇后
//    public static boolean[] dg = new boolean[N];
//    //用udg数组记录该反对角线是否放置过皇后
//    public static boolean[] udg = new boolean[N];
//
//    public static void main(String[] args) {
//        //根据题目要求读入n的值
//        Scanner in = new Scanner(System.in);
//        n = in.nextInt();
//        //将g数组初始化为未放置任何皇后的情况
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                g[i][j] = '.';
//            }
//        }
//        //调用dfs函数
//        dfs(0);
//    }
//
//
//    public static void dfs(int u) {//u用来记录现在在第几层
//        if (u == n) {//如果已经触底
//            for (int i = 0; i < n; i++) System.out.println(g[i]);
//            return;
//        }
//        for (int i = 0; i < n; i++) {//循环遍历每一个位置
//            if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
//                //当当前位置的列、正对角线、反对角线都未被放置皇后时
//                col[i] = dg[u + i] = udg[n - u + i] = true;//更改状态
//                g[u][i] = 'Q';//将该位置放置皇后
//                dfs(u + 1);//搜索下一层
//                //还原现场
//                col[i] = dg[u + i] = udg[n - u + i] = false;
//                g[u][i] = '.';
//            }
//        }
//    }
//}
